import math

import numpy as np
import random
import time
from collections import deque, defaultdict, OrderedDict
from MeiTuan.dispatch import *
from typing import List, Dict, Any, Set, Tuple
from ortools.graph.python import min_cost_flow
from pulp import LpProblem, LpVariable, LpMinimize, LpBinary, PULP_CBC_CMD
import os
import sys
current_path = os.path.split(os.path.realpath(__file__))[0]
sys.path.append(current_path)
from entities import *
from km import *




topK = 50000
IS_PER_HOUR = True
MIN_PER_HOUR = 60
alpha = 0.025
gamma1 = 0.9
residual = 0.09
gamma2 = gamma1 + residual
time_step = 2

GRID_NUM = 8519
# DIRS = [[0, 0], [0, 1], [1, 0], [-1, 0], [0, -1], [1, 1], [1, -1], [-1, 1], [-1, -1]]
DIRS = [[3, 1], [1, -3], [-3, -1], [-1, 3], [0, 0]]
# DIRS = [[0, 0], [0, 1], [1, 0], [0, -1], [-1, 0]]
DIR_NUM = len(DIRS)
SPEED = 3 * 2

REPO_NAIVE = True   # True: use naive reposition algorithm
QUICK = True       # True: use probability quick version
INIT_VALUE = False


INIT_GRID = False # initial values for grid values
TIME_INTERVAL = 10

IS_CLEAR = True # clear up the values when day_of_week changes
dx =  [1, -1, 0, 0, 0] # [-1, -1, 1,-1, 1, -1, 0, 0, 0] #
dy =  [0, 0, -1, 1, 0] # [1, -1, 1, -1, 0, 0, -1, 1, 0] #

def acc_dist(start_pos, end_pos, env_type="Grid") -> float:
    if env_type == "GIS":
        start_x, start_y = start_pos
        end_x, end_y = end_pos
        delta_lat = (start_x - end_x) / 2
        delta_lng = (start_y - end_y) / 2
        arc_pi = 3.14159265359 / 180
        R = 6378137
        return 2 * R * math.asin(math.sqrt(
            math.sin(arc_pi * delta_lat) ** 2 + math.cos(arc_pi * start_x) * math.cos(arc_pi * end_x) * (
                    math.sin(arc_pi * delta_lng) ** 2)))
    elif env_type =="Grid":
        return abs(start_pos.x-end_pos.x) + abs(start_pos.y-end_pos.y)

def get_topK(dispatch_observ, k=10):
    order_to_dis_idx = dict()
    dispatch_observ_after_sift = []
    for i in range(len(dispatch_observ)):
        elem = dispatch_observ[i]
        if elem['order_id'] not in order_to_dis_idx:
            order_to_dis_idx[elem['order_id']] = []
        order_to_dis_idx[elem['order_id']].append((elem['order_driver_distance'], i))
    for key in order_to_dis_idx:
        order_to_dis_idx[key].sort()
        for j in range(min(k, len(order_to_dis_idx[key]))):
            dispatch_observ_after_sift.append(dispatch_observ[order_to_dis_idx[key][j][1]])
    return dispatch_observ_after_sift

    
def cal_income(driver_id, cur_hour, drivers_total_income, drivers_income_per_hour, per_hour=True):
    return drivers_income_per_hour[driver_id][cur_hour] if per_hour else drivers_total_income[driver_id]

def cal_online_seconds(hour_on, cur, dur=0, per_hour=True):
    # print("time", (log_on + 3599) // 3600 * 3600 )
    cur_hour = (cur // 3600) % 24
    total = sum([hour_on[i] for i in range(cur_hour)]) * 60
    # print("________________",hour_on, cur_hour, cur )
    return total + dur if not per_hour else hour_on[cur_hour] * 60 + dur
    #return (cur - log_on + dur) if not per_hour or cur < (log_on + 3599) // 3600 * 3600 else cur % 3600 + dur

def GreedyAlgorithm(dispatch_observ: List[Dict[str, Any]]) -> List[Dict[str, int]]:
    """ Compute the assignment between drivers and passengers at each time step
        :param dispatch_observ: a list of dict, the key in the dict includes:
                order_id, int
                driver_id, int
                reward_units, float
        :return: a list of dict, the key in the dict includes:
                order_id and driver_id, the pair indicating the assignment
    """
    dispatch_observ.sort(key=lambda od_info: -od_info['reward_units'])
    assigned_order = set()
    assigned_driver = set()
    dispatch_action = []
    for od in dispatch_observ:
        # make sure each order is assigned to one driver, and each driver is assigned with one order
        if (od["order_id"] in assigned_order) or (od["driver_id"] in assigned_driver):
            continue
        assigned_order.add(od["order_id"])
        assigned_driver.add(od["driver_id"])
        dispatch_action.append(dict(order_id=od["order_id"], driver_id=od["driver_id"]))
    return dispatch_action

def DistanceGreedyAlgorithm(dispatch_observ: List[Dict[str, Any]]) -> List[Dict[str, int]]:
    """ Compute the assignment between drivers and passengers at each time step
        :param dispatch_observ: a list of dict, the key in the dict includes:
                order_id, int
                driver_id, int
                order_driver_distance, float
        :return: a list of dict, the key in the dict includes:
                order_id and driver_id, the pair indicating the assignment
    """
    dispatch_observ.sort(key=lambda od_info: -od_info['order_driver_distance'])
    assigned_order = set()
    assigned_driver = set()
    dispatch_action = []
    for od in dispatch_observ:
    # make sure each order is assigned to one driver, and each driver is assigned with one order
        if (od["order_id"] in assigned_order) or (od["driver_id"] in assigned_driver):
            continue
        assigned_order.add(od["order_id"])
        assigned_driver.add(od["driver_id"])
        dispatch_action.append(dict(order_id=od["order_id"], driver_id=od["driver_id"]))
    return dispatch_action

def NearestNeighborPriority(dispatch_observ: List[Dict[str, Any]]) -> List[Dict[str, int]]:
    """ Compute the assignment between drivers and passengers at each time step
    :param dispatch_observ: a list of dict, the key in the dict includes:
                order_id, int
                driver_id, int
                order_driver_distance, float
    :return: a list of dict, the key in the dict includes:
                order_id and driver_id, the pair indicating the assignment
    """
    dispatch = []
    global_num = 2
    order2idx = dict()
    idx2order = dict()
    driver2idx = dict()
    idx2driver = dict()
    for od in dispatch_observ:
        order_id = od['order_id']
        driver_id = od['driver_id']
        if order_id not in order2idx:
            order2idx[order_id] = global_num
            idx2order[global_num] = order_id
            global_num += 1
        if driver_id not in driver2idx:
            driver2idx[driver_id] = global_num
            idx2driver[global_num] = driver_id
            global_num += 1
    start_nodes = []
    end_nodes = []
    capacities = []
    unit_costs = []
    for od in dispatch_observ:
        order_idx = order2idx[od['order_id']]
        driver_idx = driver2idx[od['driver_id']]
        cost = int(od['order_driver_distance'])
        start_nodes.append(order_idx)
        end_nodes.append(driver_idx)
        unit_costs.append(cost)
        capacities.append(1)

    src = 0
    dst = 1
    for order_idx in idx2order:
        start_nodes.append(src)
        end_nodes.append(order_idx)
        unit_costs.append(0)
        capacities.append(1)

    for driver_idx in idx2driver:
        start_nodes.append(driver_idx)
        end_nodes.append(dst)
        unit_costs.append(0)
        capacities.append(1)
    mincostflow = min_cost_flow.SimpleMinCostFlow()
    for i in range(0, len(start_nodes)):
        mincostflow.add_arc_with_capacity_and_unit_cost(start_nodes[i], end_nodes[i], capacities[i], unit_costs[i])
    mincostflow.set_nodes_supplies(0, min(len(order2idx), len(driver2idx)))
    mincostflow.set_nodes_supplies(1, -min(len(order2idx), len(driver2idx)))
    mincostflow.solve_max_flow_with_min_cost()
    for i in range(mincostflow.num_arcs()):
        if mincostflow.flow(i) > 0.1:
            if mincostflow.tail(i) != 0 and mincostflow.head(i) != 1:
                dispatch.append(dict(order_id=idx2order[mincostflow.tail(i)], driver_id=idx2driver[mincostflow.head(i)]))
    return dispatch

def HungarianAlgorithm(dispatch_observ: List[Dict[str, Any]]) -> List[Dict[str, str]]:
    """ Compute the assignment between drivers and passengers at each time step
        :param dispatch_observ: a list of dict, the key in the dict includes:
                order_id, int
                driver_id, int
                reward_units, float
        :return: a list of dict, the key in the dict includes:
                order_id and driver_id, the pair indicating the assignment
    """
    if len(dispatch_observ) == 0:
        return []
    values = [(each['driver_id'], each['order_id'], each['reward_units']) for each in dispatch_observ]
    val, dispatch_tuple = find_max_match(x_y_values=values, split=False, quick=False)
    return [dict(driver_id=each[0], order_id=each[1]) for each in dispatch_tuple]

def WorstOffDriverFirst(dispatch_observ: List[Dict[str, Any]], drivers_income_per_hour = defaultdict(lambda: [0 for i in range(25)]) ) -> List[Dict[str, int]]:
    """ Compute the assignment between drivers and passengers at each time step
    :param dispatch_observ: a list of dict, the key in the dict includes:
            order_id, int
            driver_id, int
            order_driver_distance, float
            timestamp, int

    :param drivers_income_per_hour:  a dict, the key in the dict includes:
            driver_id , a list as [the driver's income in 1:00 am ....], float


    :return: a list of dict, the key in the dict includes:
            order_id and driver_id, the pair indicating the assignment
    """
    # record orders of each driver, add driver into utility recorder
    if len(dispatch_observ) == 0:
        return []
    timestamp = dispatch_observ[0]['timestamp']
    current_hour = int(timestamp / 60) % 24
    driver_to_orders = defaultdict(list)
    for od in dispatch_observ:
        pref = od['order_distance']+ od['order_driver_distance']
        driver_to_orders[od['driver_id']].append((pref, od['order_id']))

    # make the right order of drivers based on utility
    # caution: only consider drivers in this round
    utility_driver_worst_first = [(drivers_income_per_hour[driver_id][current_hour], driver_id)
                                      for driver_id in driver_to_orders]
    utility_driver_worst_first.sort()
    # same utility need shuffling
    i = 0
    while i < len(utility_driver_worst_first) - 1:
        j = i + 1
        while j < len(utility_driver_worst_first) and \
            abs(utility_driver_worst_first[j][0] - utility_driver_worst_first[i][0]) < 0.000005:
            j += 1
        if j - i > 1:
            copy = utility_driver_worst_first[i:j]
            random.shuffle(copy)
            utility_driver_worst_first[i:j] = copy
        i = j

    # worst first matching
    assigned_orders = set()
    dispatch_action = []
    for utility, driver_id in utility_driver_worst_first:
        # sort based on pref from high to low
        driver_to_orders[driver_id].sort(reverse=True)
        for pref, order_id in driver_to_orders[driver_id]:
            if order_id in assigned_orders:
                continue
            assigned_orders.add(order_id)
            dispatch_action.append(dict(order_id=order_id, driver_id=driver_id))
            break
    return dispatch_action

def IntegerLinearProgramming(dispatch_observ: List[Dict[str, Any]], drivers_utility : defaultdict(float),
                             driver_online_rounds: defaultdict(int), driver_max_last_round :int ) -> List[Dict[str, int]]:
    """ Compute the assignment between drivers and passengers at each time step
    :param dispatch_observ: a list of dict, the key in the dict includes:
            order_id, int
            driver_id, int
            order_driver_distance, float
            timestamp, int
            order_finish_timestamp, int
            reward_units, float

    :param drivers_utility: a dict the key in the dict includes:
            driver_id, the utility of the driver, float
    :param driver_online_rounds: a dict the key in the dict includes:
            driver_id, the rounds, int
    :param driver_max_last_round: int
    :return: a list of dict, the key in the dict includes:
                rder_id and driver_id, the pair indicating the assignment
    """
    if len(dispatch_observ) == 0:
        return [], drivers_utility, driver_online_rounds, driver_max_last_round
    cur_min = dispatch_observ[0]['timestamp']
    # cur_local = time.localtime(timestamp)
    od_decision = dict()                # type: Dict[str, Any]
    if_match_utility = dict()           # type: Dict[str, float]
    drivers_cur_round = set()           # type: Set[int]
    orders_cur_round = set()            # type: Set[int]
    order_driver_cand = defaultdict(int)
    dispatch_observ.sort(key=lambda x: x['order_driver_distance'])
    for od in dispatch_observ:
        driver_id = od['driver_id']     # type: int
        order_id = od['order_id']       # type: int
        orders_cur_round.add(order_id)
        if order_driver_cand[order_id] < topK:
            order_driver_cand[order_id] += 1
            drivers_cur_round.add(driver_id)
            driver_id_order_id = str(driver_id) + "_" + str(order_id)  # type: str
            od_decision[driver_id_order_id] = LpVariable(cat=LpBinary, name=driver_id_order_id)
            if_match_utility[driver_id_order_id] =  od['order_distance'] - od['order_driver_distance']

    # Create a new model
    m = LpProblem(name="ILP_Model", sense=LpMinimize)
    # each driver should only have at most one order
    # each order should only have at most one driver
    driver_constrains = defaultdict(int)
    order_constrains = defaultdict(int)
    goal = 0
    for driver_id_order_id in od_decision:
        driver_id, order_id = driver_id_order_id.split('_')
        driver_constrains[driver_id] += od_decision[driver_id_order_id]
        order_constrains[order_id] += od_decision[driver_id_order_id]
        one_driver = driver_max_last_round - \
                    (drivers_utility[driver_id] / (driver_online_rounds[driver_id] + 1)
                    + od_decision[driver_id_order_id] * if_match_utility[driver_id_order_id] /
                    (driver_online_rounds[driver_id] + 1))

        one_driver_abs = LpVariable(name="abs_driver" + driver_id_order_id)
        m += (one_driver_abs >= one_driver)
        m += (one_driver_abs >= -one_driver)
        goal += one_driver_abs
    for driver_id in driver_constrains:
        m += (driver_constrains[driver_id] <= 1)
    for order_id in order_constrains:
        m += (order_constrains[order_id] <= 1)
    m += goal
    m.solve(PULP_CBC_CMD(msg=False))
    # update the online rounds
    if cur_min == 0 :
        for driver_id in drivers_cur_round:
            driver_online_rounds[driver_id] = 0
        for driver_id in drivers_utility:
            drivers_utility[driver_id] = 0
    for driver_id in drivers_cur_round:
        driver_online_rounds[driver_id] += 1
    dispatch_action = []    # type: List[Dict[str, int]]
    for v in m.variables():
        if v.varValue == 0:
            try:
                driver_id_str, order_id_str = v.name.split('_')
            except ValueError:            
                continue
            # print("#####", driver_id, order_id)
            dispatch_action.append(dict(order_id=int(order_id_str), driver_id=int(driver_id_str)))
                # update the utility
            drivers_utility[int(driver_id_str)] += if_match_utility[driver_id_str + '_' + order_id_str]
            driver_max_last_round = max(driver_max_last_round,
                                                    drivers_utility[int(driver_id_str)] / driver_online_rounds[int(driver_id_str)])
    return dispatch_action, drivers_utility, driver_online_rounds, driver_max_last_round

def Reassign(dispatch_observ: List[Dict[str, Any]], drivers_total_income: Dict[int, float], drivers_online_per_hour: Dict[int, list], 
             drivers_income_per_hour= defaultdict(lambda: [0 for i in range(25)])) -> List[Dict[str, int]]:
    """ Compute the assignment between drivers and passengers at each time step
    :param dispatch_observ: a list of dict, the key in the dict includes:
            order_id, int
            driver_id, int
            order_driver_distance, float
            order_start_location, a list as [lng, lat], float
            order_finish_location, a list as [lng, lat], float
            timestamp, int
            order_finish_timestamp, int
            reward_units, float

    :param drivers_total_income:  the driver's income. a dict, the key in the dict includes:
            driver_id , the driver's income(float)
    :param drivers_online_per_hour: a dict, with key is driver's id, value is online time (in seconds)
    :param drivers_income_per_hour:  a dict, the key in the dict includes:
            driver_id , a list as [the driver's income in 1:00 am ....], float

    :return: a list of dict, the key in the dict includes:
            order_id and driver_id, the pair indicating the assignment
    """
    if len(dispatch_observ) == 0:
        return []
    # cur_time = time.localtime(dispatch_observ[0]['timestamp'])
    cur_sec = dispatch_observ[0]['timestamp'] * 60 #(cur_time.tm_hour - 4) * 3600 + cur_time.tm_min * 60 + cur_time.tm_sec
    cur_hour = (cur_sec // 3600) % 24

    drivers = set(each['driver_id'] for each in dispatch_observ)
    orders = set(each['order_id'] for each in dispatch_observ)
    order_to_dur = defaultdict(int)
    for each in dispatch_observ:
        order_to_dur[each['order_id']] = (each['order_finish_timestamp'] - each['timestamp']) * 60
    order_to_pri = {each['order_id']: each['reward_units'] for each in dispatch_observ}
    fake_edges = [(driver, int("8888" + str(driver)), 0) for driver in drivers]
    edges = [(each['driver_id'], each['order_id'], each['reward_units']) for each in dispatch_observ]
    edge_plus = edges + fake_edges
    # get M_old
    v, match_old = find_max_match(edges, split = False)
    match_old_dic = {each[0]: each[1] for each in match_old}
    # get M_fair  bi search for edge weights
    match_fair = match_old
    lo, hi = 0, 50
    while abs(lo - hi) > 0.001:
        f = (lo + hi) / 2
        edge_f = [edge for edge in edge_plus if (cal_income(edge[0], cur_hour,
                                                                drivers_total_income,
                                                                drivers_income_per_hour, IS_PER_HOUR)
                                                     + edge[2]) /
                      (cal_online_seconds(drivers_online_per_hour[edge[0]],
                                         cur_sec, order_to_dur[edge[1]], IS_PER_HOUR) + 0.1) > f]
        v_f, match_fair = find_max_match(edge_f, split = False)
        perfect_match = True
        if len(match_fair) < min(len(order_to_dur), len(drivers)):
            perfect_match = False
        if perfect_match:
            lo = f
        else:
            hi = f
    match_fair_dic = {each[0]: each[1] for each in match_fair if each[2] > 0.000001}
    f_opt = lo
    # get f_threshold
    driver_incomes = [cal_income(driver, cur_hour,
                                     drivers_total_income, drivers_income_per_hour, IS_PER_HOUR)
                          for driver in drivers]
    driver_incomes.sort()
    f_thresh = driver_incomes[int(len(driver_incomes) * 0.1)]
    if f_thresh < 0.00001:
        match_new_dic = match_old_dic
    elif f_thresh > f_opt:
        match_new_dic = match_fair_dic
    else:
        # reassign
        match_new_dic = match_old_dic
        break_loop = 0
        while True:
            break_loop += 1
            for driver in match_new_dic:
                order = match_new_dic[driver]
                price = order_to_pri[order]
                #fairness check
                if (cal_income(driver, cur_hour,
                            drivers_total_income, drivers_income_per_hour, IS_PER_HOUR) + price) / \
                        (cal_online_seconds(drivers_online_per_hour[driver],
                                                cur_sec, order_to_dur[order], IS_PER_HOUR) + 0.1) < f_thresh:
                    v = driver
                    break
            else:
                break
            match_new_dic.pop(v)
            if v not in match_fair_dic:
                continue
            while True:
                break_loop += 1
                for driver in match_new_dic:
                    try:
                        if match_new_dic[driver] == match_fair_dic[v]:
                            vp = driver
                            break
                    except KeyError:
                        print(driver, v in  match_fair_dic)
                        raise KeyError(driver, v, match_new_dic.keys(), match_fair_dic.keys()  )
                else: 
                    break
                match_new_dic.pop(vp)
                match_new_dic[v] = match_fair_dic[v]
                v = vp
                if v not in match_fair_dic:
                    print("may cause dead loop")
                    break
                if break_loop > 1000000:
                    print("may cause dead loop")
                    break
            if v not in match_fair_dic:
                    print("may cause dead loop")
                    break
            match_new_dic[v] = match_fair_dic[v]
            if break_loop > 1000000:
                print("may cause dead loop")
                break
    res = []
    assigned_orders = set()
    assigned_drivers = set()
    for driver in drivers:
        if driver in match_new_dic and (len(str(match_new_dic[driver])) < 4 or
                                            str(match_new_dic[driver])[0:4] != "8888"):
            res.append(dict(driver_id=driver, order_id=match_new_dic[driver]))
            assigned_drivers.add(driver)
            assigned_orders.add(match_new_dic[driver])
    dispatch_observ.sort(key=lambda x: x['order_driver_distance'])
    for each in dispatch_observ:
        if each['driver_id'] not in assigned_drivers and each['order_id'] not in assigned_orders:
            res.append(dict(driver_id=each['driver_id'], order_id=each['order_id']))
            assigned_orders.add(each['order_id'])
            assigned_drivers.add(each['driver_id'])
    print(len(res), len(dispatch_observ))
    return res

class RLdispatcher:
    def __init__(self, alpha, gamma):
        self.alpha = alpha
        self.gamma = gamma
        self.grid_values = defaultdict(float)
        self.layer_values  = defaultdict(float)
    
    # def adjust_learning_rate(self, time = 0):
    #     if time == 400:
    #         self.alpha = self.alpha / 5

    def LTD(self, dispatch_observ: List[Dict[str, Any]], drivers_online_per_hour = None, drivers_income_per_hour=None, utility_type = 'utility') -> List[Dict[str, str]]:
        if len(dispatch_observ) == 0:
            return []

        # self.cur_discrete_time = discrete_time(dispatch_observ[0]['timestamp'])
        # if self.dow != dispatch_observ[0]['day_of_week']:
        #     self.dow = dispatch_observ[0]['day_of_week']
        #     if IS_CLEAR:
        #         self.grid_values = defaultdict(float)
        #         self.layer_values = defaultdict(float)
        # self.adjust_learning_rate(dispatch_observ[0]['timestamp'])
        cur_sec = dispatch_observ[0]['timestamp'] * 60
        drivers, orders, pairs = self.parse_dispatch(dispatch_observ)
        edges = []  # type: List[Pair]
        for key in pairs:  # type: str
            pair = pairs[key]  # type: Pair
            order = orders[pair.order_id]
            driver = drivers[pair.driver_id]
            duration = int(1. * pair.duration / TIME_INTERVAL)
            duration = max(1, duration)
            v0 = self.get_smoothed_value(driver.loc)
            v1 = self.get_smoothed_value(order.finish_loc)
            # done_prob = finish_prob(pair.od_distance, order.start_loc, order.finish_loc, order.start_time)

            # if done_prob > 0:
            gamma = math.pow(self.gamma, duration)
            complete_update = order.reward + gamma * v1 - v0

            # expected_update = done_prob * complete_update
            pair.redefine_weight(complete_update)
            edges.append(pair)

        # Assign drivers
        assigned_driver_ids = set()  # type: Set[str]
        # begin hungary
        driver_order_to_score = {str(each.driver_id) + '#' + str(each.order_id): each.weight for each in edges}
        values = [(each.driver_id, each.order_id, each.weight) for each in edges]
        if utility_type == "fairness":
            olt = {driver.driver_id: cal_online_seconds(drivers_online_per_hour[driver.driver_id], cur_sec,
                                                        per_hour=True)
                for driver in drivers.values()}

            inc = {driver.driver_id: drivers_income_per_hour[driver.driver_id][cur_sec // 3600]
                for driver in drivers.values()}

            ratios = [inc[driver] / ((olt[driver] + 0.1) / 3600) for driver in drivers]
            ratios.sort()
           
            num = len(ratios)
            interval = [ratios[0], ratios[int(num * 0.25)], ratios[num // 2], ratios[int(num * 0.75)], ratios[-1]]
            order_price_dur = {order.order_id: (order.reward, order.finish_time - order.start_time) for order in orders.values()}
            val, dispatch_tuple = find_max_match(x_y_values=values, online_time=olt, income=inc,
                                                interval=interval, order_price_dur=order_price_dur,
                                                split=True,  utility_type = utility_type)
           
        else:
            val, dispatch_tuple = find_max_match(x_y_values=values, split=True, quick=True)
        dispatch = [dict(driver_id=each[0], order_id=each[1]) for each in dispatch_tuple]
        for each in dispatch:
            assigned_driver_ids.add(each['driver_id'])
            driver = drivers[each['driver_id']]
            key = str(each['driver_id']) + '#' + str(each['order_id'])
            if key in driver_order_to_score:
                score = driver_order_to_score[key]
                self.update_value(driver.loc, self.alpha * score)

        for driver in drivers.values():
            if driver.driver_id in assigned_driver_ids:
                continue
            v0 = self.get_smoothed_value(driver.loc)
            v1 = v0
            update = self.gamma * v1 - v0  # no reward
            self.update_value(driver.loc,  self.alpha * update)
        return dispatch

    def get_grid_ids(self) -> Set[str]:
        return set(self.grid_values.keys())

    def get_grid_value(self, grid_id: str) -> float:
        return self.grid_values[grid_id]

    def get_smoothed_value(self, pos: Tuple[int, int]) -> float:
        value = self.grid_values[str(pos.x)+"_"+str(pos.y)]
        for i in range(len(dx)):
            value += self.layer_values[str(pos.x + dx[i])+"_"+str(pos.y+dy[i])]           
        return value / (1 + len(dx))

    def update_value(self, pos: Tuple[int, int], delta: float) -> None:
        self.grid_values[str(pos.x)+"_"+str(pos.y)]+= delta
        for i in range(len(dx)):
            self.layer_values[str(pos.x + dx[i])+"_"+str(pos.y+dy[i])] += delta

    @staticmethod
    def parse_dispatch(dispatch_observ: List[Dict[str, Any]]) -> (Dict[str, DriverEntity], Dict[str, OrderEntity], Dict[str, Set[Pair]]):
        drivers = OrderedDict()  # type: collections.OrderedDict[str, Driver]
        orders = OrderedDict()  # type: collections.OrderedDict[str, Order]
        pairs = OrderedDict()  # type: collections.OrderedDict[str, Pair]
        for pair_raw in dispatch_observ:
            driver = DriverEntity(pair_raw)
            drivers[driver.driver_id] = driver
            order = OrderEntity(pair_raw)
            orders[order.order_id] = order
            key = str(order.order_id) + "#" + str(driver.driver_id)
            pairs[key] = Pair(pair_raw)
        return drivers, orders, pairs
    
    def reposition(self, repo_observ: Dict[str, Any],
                   drivers_total_income, drivers_online_per_hour, drivers_income_per_hour, grid) -> List[Dict[str, str]]:

        if len(repo_observ['driver_info']) == 0:
            return []
        cur_hour, cur_time, drivers = self.parse_repo(repo_observ, drivers_total_income,
                                                                         drivers_online_per_hour, drivers_income_per_hour)
        # grid_ids = Grid.get_grid_ids()
        drivers.sort(key=lambda x: x[2])  # sort from small to large based on ratio
        median = drivers[int(len(drivers) * 0.50)][2]
        reposition = []  # type: List[Dict[str, str]]
        for driver_id, current_grid_pos, ratio in drivers:

            if 6 <= ratio <= 12:
                reposition.append(dict(driver_id=driver_id, destination=(current_grid_pos.x, current_grid_pos.y)))
            else:
                best_grid_pos, best_value = (current_grid_pos.x, current_grid_pos.y), -100
                current_value = self.get_grid_value(str(current_grid_pos.x)+"_"+str(current_grid_pos.y))
                for grid_pos in grid.move_map:
                    # duration = acc_dist(current_grid_pos, DiscretePoint(grid_pos[0], grid_pos[1])) / SPEED
                    if (current_grid_pos.x, current_grid_pos.y) == grid_pos:
                        duration = 0
                    else:
                        duration = (len(grid.paths[str((current_grid_pos.x, current_grid_pos.y))][str(grid_pos)] )-1) 
                    if ratio < 6:
                        discount = math.pow(0.999, duration)
                        proposed_value = self.get_grid_value(str(grid_pos[0])+"_"+str(grid_pos[1]))
                        incremental_value = discount * proposed_value - current_value
                    else:
                        incremental_value = -abs(median -
                                                 drivers_income_per_hour[driver_id][cur_hour] /
                                                 ((cal_online_seconds(
                                                     drivers_online_per_hour[driver_id], cur_time, duration,
                                                     per_hour=False) + 0.1)
                                                  / 3600))
                    if incremental_value > best_value:
                        best_grid_pos, best_value = grid_pos, incremental_value

                reposition.append(dict(driver_id=driver_id, destination=best_grid_pos))
        return reposition

    @staticmethod
    def parse_repo(repo_observ, drivers_total_income, drivers_online_per_hour, drivers_income_per_hour):
        timestamp = repo_observ['timestamp']  # type: int
        cur_time = timestamp * 60
        drivers = [(driver['driver_id'], driver['position'],
                    drivers_income_per_hour[driver['driver_id']][cur_time // 3600] /
                    ((cal_online_seconds(drivers_online_per_hour[driver['driver_id']], cur_time, per_hour=False) + 0.1) / 3600))
                   for driver in repo_observ['driver_info']]  # type: List[Tuple[str, str, float]]
        return cur_time // 3600, cur_time, drivers


def handle_dispatch(dispatch_action, model):
    orders = []
    for order in model.meituan.normal_orders:  # 改为只为普通订单调度
        for o in order:
            orders.append(o)
    for pair in dispatch_action:
        order_id = pair["order_id"]
        rider = self.context.agent((pair["driver_id"], 1, 0))
        order = next(o for o in orders if o.id == order_id)
        # 如果订单已处理或骑手订单数达到限制，则跳过
        if order.status == 'processed' or rider.order_count >= rider.max_orders:
            continue

        # 检查插入的位置是否合法，对于送货事件，还要检查取货事件是否已经在路线中
        valid_positions = []
        for i in range(len(rider.route) + 1):
            new_route = rider.route[:i] + [(event_type, order_id)] + rider.route[i:]
            if is_valid_route(new_route, orders):
                # 对于送货事件，确保其对应的取货事件已经在路线中
                if event_type == 'delivery' and not any(et == 'pickup' and oid == order_id for et, oid in new_route):
                    continue
                valid_positions.append((i, objective(new_route, orders, current_time, current_location)))

        # 如果没有有效位置，则跳过此订单
        if not valid_positions:
            continue

        # 选择目标函数值最小的位置
        best_position, best_value = min(valid_positions, key=lambda x: x[1])

        # 更新骑手的路线，订单状态和骑手的订单计数
        rider.route = rider.route[:best_position] + [(event_type, order_id)] + rider.route[best_position:]
        # 更新订单的取送货状态
        order_status[order_id][event_type] = True
        # 检查是否两个事件都完成了，如果是，则更新订单状态和骑手订单计数
        if all(order_status[order_id].values()):
            order.status = 'processed'
            rider.order_count += 1  # 完成一个完整的订单，骑手订单计数增加1
            rider.check += 1
